import heapq

class ParkingScheduler:
    def __init__(self, parking_spots):
        """
        初始化停车场调度系统
        :param parking_spots: 车位列表，每个元素为(距离入口距离, 车位编号)
        """
        # 使用最小堆管理空闲车位（按距离排序）
        self.available_spots = []
        for distance, spot_id in parking_spots:
            heapq.heappush(self.available_spots, (distance, spot_id))
        
        # 记录占用中的车位 {车位编号: (车辆ID, 离开时间)}
        self.occupied_spots = {}
    
    def assign_spot(self, vehicle_id, arrival_time, duration):
        """
        为车辆分配车位（贪心算法：选择最近的可用车位）
        :param vehicle_id: 车辆ID
        :param arrival_time: 到达时间（格式: 'HH:MM'）
        :param duration: 停留时长（小时）
        :return: (分配的车位编号, 预计离开时间)
        :raises: ValueError 如果没有可用车位
        """
        if not self.available_spots:
            raise ValueError("没有可用车位")
            
        # 获取最近的车位
        distance, spot_id = heapq.heappop(self.available_spots)
        
        # 计算离开时间
        leave_time = self._calculate_leave_time(arrival_time, duration)
        
        # 记录占用信息
        self.occupied_spots[spot_id] = (vehicle_id, leave_time)
        
        return spot_id, leave_time
    
    def release_spot(self, spot_id):
        """释放车位，将其重新加入可用队列"""
        if spot_id in self.occupied_spots:
            distance = self._get_distance_by_spot_id(spot_id)
            heapq.heappush(self.available_spots, (distance, spot_id))
            del self.occupied_spots[spot_id]
    
    def _calculate_leave_time(self, arrival_time, duration):
        """计算离开时间（确保格式为HH:MM）"""
        hours, minutes = map(int, arrival_time.split(':'))
        total_minutes = hours * 60 + minutes + int(duration * 60)
        # 处理24小时制转换
        leave_hour = total_minutes // 60 % 24
        leave_min = total_minutes % 60
        return f"{leave_hour:02d}:{leave_min:02d}"
    
    def _get_distance_by_spot_id(self, spot_id):
        """根据车位ID查找距离"""
        for dist, sid in self.available_spots:
            if sid == spot_id:
                return dist
        for sid, (_, _) in self.occupied_spots.items():
            if sid == spot_id:
                return 50  # 默认距离，实际应从初始化数据获取
        return 50

if __name__ == "__main__":
    # 测试用例
    print("=== 贪心算法测试 ===")
    parking_spots = [(50, 1), (100, 2), (150, 3), (200, 4)]
    scheduler = ParkingScheduler(parking_spots)
    
    # 测试1: 正常分配车位
    result1 = scheduler.assign_spot("A1", "09:00", 2)
    print(f"测试1 - 车辆A1分配到车位 {result1[0]} (预期: 1)，预计离开时间 {result1[1]} (预期: 11:00)")
    
    # 测试2: 分配第二个车位
    result2 = scheduler.assign_spot("B2", "10:30", 1.5)
    print(f"测试2 - 车辆B2分配到车位 {result2[0]} (预期: 2)，预计离开时间 {result2[1]} (预期: 12:00)")
    
    # 测试3: 释放车位1
    scheduler.release_spot(1)
    print(f"测试3 - 车位1已释放，当前可用车位: {[spot[1] for spot in scheduler.available_spots]} (预期包含: [1])")
    
    # 测试4: 再次分配应优先使用最近释放的车位1
    result4 = scheduler.assign_spot("C3", "13:00", 3)
    print(f"测试4 - 车辆C3分配到车位 {result4[0]} (预期: 1)，预计离开时间 {result4[1]} (预期: 16:00)")
    
    # 测试5: 跨午夜时间计算
    result5 = scheduler.assign_spot("D4", "23:45", 0.25)
    print(f"测试5 - 车辆D4分配到车位 {result5[0]}，预计离开时间 {result5[1]} (预期: 00:00)")
    
    print("=== 测试完成 ===")
